A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization

摘要

Non-negative matrix factorization (NMF) is the problem of determining twonon-negative low rank factors $W$ and $H$, for the given input matrix $A$, suchthat $A \approx W H$. NMF is a useful tool for many applications in differentdomains such as topic modeling in text mining, background separation in videoanalysis, and community detection in social networks. Despite its popularity inthe data mining community, there is a lack of efficient parallel software tosolve the problem for big datasets. Existing distributed-memory algorithms arelimited in terms of performance and applicability, as they are implementedusing Hadoop and are designed only for sparse matrices. We propose a distributed-memory parallel algorithm that computes thefactorization by iteratively solving alternating non-negative least squares(NLS) subproblems for $W$ and $H$. To our knowledge, our algorithm is the firsthigh-performance parallel algorithm for NMF. It maintains the data and factormatrices in memory (distributed across processors), uses MPI for interprocessorcommunication, and, in the dense case, provably minimizes communication costs(under mild assumptions). As opposed to previous implementations, our algorithmis also flexible: (1) it performs well for dense and sparse matrices, and (2)it allows the user to choose from among multiple algorithms for solving localNLS subproblems within the alternating iterations. We demonstrate thescalability of our algorithm and compare it with baseline implementations,showing significant performance improvements.